/*
    快速幂、矩阵快速幂与两类问题

    前置知识
    讲解005、讲解042 - 对数器、对数器打表找规律，本节课题目5需要
    讲解041 - 同余原理
    讲解066、讲解067、讲解068、讲解069 - 动态规划基础

    乘法快速幂，在讲解090讲过，会的同学可以跳过
    矩阵乘法、矩阵快速幂，题目2、3、4、5、6、7
    固定关系的1维k阶递推表达式，用矩阵快速幂求解时间复杂度O(logn * k的3次方)，题目2、3、4、5
    固定关系的k维1阶递推表达式，用矩阵快速幂求解时间复杂度O(logn * k的3次方)，题目6、7

    注意：
    讲解097、讲解098、讲解099，可以称为"不用多问为什么"专题
    有兴趣可以翻帖子看证明，用纸和笔跟着推一遍是最好的方式
    因为证明麻烦，并且证明过程没啥扩展性，记住用法和模版即可，当做原子技能使用

    ================================================

    题目1
    乘法快速幂模版
    求a的b次方，对p取模的结果
    测试链接 : https://www.luogu.com.cn/problem/P1226

    如果a是固定位数，并且结果要求取模，那么任何中间结果也都是固定位数

    那么求a的n次方取模后的结果，使用乘法快速幂可以做到时间复杂度O(logn)

    讲解041 - 同余原理

    ================================================

    题目2
    求斐波那契数列第n项
    测试链接 : https://leetcode.cn/problems/fibonacci-number/

    矩阵乘法
    矩阵快速幂
    固定关系的1维1阶递推表达式，很明显可以用乘法快速幂解决，时间复杂度O(logn)，可以推广到1维多阶
    固定关系的1维k阶递推表达式，可以用矩阵快速幂解决，时间复杂度O(logn * k的三次方)
    关系矩阵的第0列直接由递推表达式确定，剩下的项可以用前面的初始项带入求出
    非常全的代码展示，本节Code02_BigShow文件

    本题为固定关系的1维2阶递推表达式，矩阵快速幂加速求解，时间复杂度O(logn * 2的3次方)

    ================================================

    题目3
    爬楼梯
    假设你正在爬楼梯，每次你可以爬1或2个台阶
    你有多少种不同的方法可以爬到n层
    测试链接 : https://leetcode.cn/problems/climbing-stairs/

    关系矩阵的第0列直接由递推表达式确定，剩下的项可以用前面的初始项带入求出

    本题为固定关系的1维2阶递推表达式，矩阵快速幂加速求解，时间复杂度O(logn * 2的3次方)

    ================================================

    题目4
    第n个泰波那契数
    t(0) = 0, t(1) = 1, t(2) = 1
    t(i) = t(i-1) + t(i-2) + t(i-3)
    求t(n)
    测试链接 : https://leetcode.cn/problems/n-th-tribonacci-number/

    关系矩阵的第0列直接由递推表达式确定，剩下的项可以用前面的初始项带入求出

    本题为固定关系的1维3阶递推表达式，矩阵快速幂加速求解，时间复杂度O(logn * 3的3次方)

    ================================================

    题目5
    多米诺和托米诺平铺
    有两种形状的瓷砖，一种是2*1的多米诺形，另一种是形如"L"的托米诺形
    两种形状都可以旋转，给定整数n，返回可以平铺2*n的面板的方法数量
    返回对1000000007取模的值
    测试链接 : https://leetcode.cn/problems/domino-and-tromino-tiling/

    关系矩阵的第0列直接由递推表达式确定，剩下的项可以用前面的初始项带入求出

    本题用到讲解042 - 对数器打表找规律

    本题为固定关系的1维3阶递推表达式，矩阵快速幂加速求解，时间复杂度O(logn * 3的3次方)

    ================================================

    题目5
    多米诺和托米诺平铺
    有两种形状的瓷砖，一种是2*1的多米诺形，另一种是形如"L"的托米诺形
    两种形状都可以旋转，给定整数n，返回可以平铺2*n的面板的方法数量
    返回对1000000007取模的值
    测试链接 : https://leetcode.cn/problems/domino-and-tromino-tiling/

    关系矩阵的第0列直接由递推表达式确定，剩下的项可以用前面的初始项带入求出

    本题用到讲解042 - 对数器打表找规律

    本题为固定关系的1维3阶递推表达式，矩阵快速幂加速求解，时间复杂度O(logn * 3的3次方)

    ================================================

    题目6
    统计元音字母序列的数目
    给你一个整数n，请你帮忙统计一下我们可以按下述规则形成多少个长度为n的字符串：
    字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
    每个元音 'a' 后面都只能跟着 'e'；每个元音 'e' 后面只能跟着 'a' 或者是 'i'
    每个元音 'i' 后面 不能 再跟着另一个 'i'；每个元音 'o' 后面只能跟着 'i' 或者是 'u'
    每个元音 'u' 后面只能跟着 'a'。由于答案可能会很大，结果对1000000007取模
    测试链接 : https://leetcode.cn/problems/count-vowels-permutation/

    固定关系的k维1阶递推表达式，用矩阵快速幂的过程，很容易理解，关系矩阵全部由递推表达式确定

    本题为固定关系的5维1阶递推表达式，矩阵快速幂加速求解，时间复杂度O(logn * 5的3次方)

    ================================================

    题目7
    学生出勤记录II
    可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）
    记录中只含下面三种字符：'A'：Absent，缺勤、'L'：Late，迟到、'P'：Present，到场
    如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
    按 总出勤 计，学生缺勤（'A'）严格 少于两天
    学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。
    给你一个整数n，表示出勤记录的长度（次数）
    请你返回记录长度为n时，可能获得出勤奖励的记录情况数量
    答案可能很大，结果对1000000007取模
    测试链接 : https://leetcode.cn/problems/student-attendance-record-ii/

    关系矩阵全部由递推表达式确定
    本题为固定关系的6维1阶递推表达式，矩阵快速幂加速求解，时间复杂度O(logn * 6的3次方)

*/